package chp;

import java.util.Vector;

public class SolutionProducer
{
	int N;
	int K;
	int[] ySet;
	WICOutput output;
	
	int[] status;
	int[][] interval;
	int numK;				/* holds the number of intervals at any particular time */
	Vector<int[]> solution = new Vector<int[]>();
	
	SolutionProducer(WICInput input)
	{
		K = input.getK();
		N = input.getN();
		ySet = input.getYSet();
		output = new WICOutput(null,-1);
		status = new int[N];				/* status of 1 would indicate that y(i) is complete */
		interval = new int[N][N];

		//TestCaseGenerator tg = new TestCaseGenerator();
		//tg.generateTestCase(N, K, "test.WIC");
		
		for(int i = 0; i < N; i++)
		{
			status[i] = -1;
		}
		
		for(int i = 0; i < N; i++)
		{
			for(int j = 0; j < N; j++)
			{
				interval[i][j] = 0;
			}
		}
	
		numK = 0;
	}

	public WICOutput getSolution()
	{
		int i, j;
		int posOfInt = 0;
		int min = 0;
		
	/* Optional Step: Reduce once by the minimum number in ySet */
	/*	
		min = findMin(ySet);
		System.out.println("Minimum Value: " + min);
		for(i = 0; i < N; i++)
		{
			ySet[i] = ySet[i] - min;
		}
		addInterval(0,N - 1,min);
//	*/
		
	/* Step 1: Part A Reduce common numbers in an interval */
	/* For example, with 7,8,9,9,9,4: the sub-sequence 9,9,9 would be recognized */
//	/*	
		for(i = 0; i < N; i++)
		{
			if(ySet[i] == 0) continue;
			
			j = i;
			while(j < N - 1)
			{
				if(ySet[j] == ySet[j+1]) 
				{
					j = j + 1;
					continue;
				}
				else break;
			}
			
			if(j - i > 0) addInterval(i,j,ySet[j]);
			i = j;
		}
//	*/
		
	/* Step 1: Part B Reduce common numbers in an interval */
	/* For example, with 7,8,8,9,9,9,8,8,8,4: the sub-sequence 8,8,9,9,9,8,8,8 would be recognized */
		
		
		
	/* Step 2: Identify 3-pattern (a,b,c) a = c */
//	/*	
		for(i = 0; i < N - 2; i++)
		{
			if((ySet[i] == 0)||(ySet[i + 1] == 0)||(ySet[i + 2] == 0)) continue;
			
			if((ySet[i] == ySet[i + 2]) && (ySet[i] < ySet[i + 1]))
			{
				//System.out.println("Found 3 pattern a = c: " + ySet[i] + ySet[i + 1] + ySet[i + 2]);
				
				
				if(status[i] != -1)
				{
					posOfInt = status[i];
					interval[posOfInt][i + 1] = ySet[i];
					status[i + 1] = posOfInt;
					
					if(status[i + 2] == -1) 
						{
							interval[posOfInt][i + 2] = ySet[i];
							status[i + 2] = posOfInt;
						}

					//System.out.println("Extended Interval ahead to: " + (i + 1) + " " + (i + 2));
				}
				
				else if(status[i + 2] != -1)
				{
					posOfInt = status[i + 2];
					interval[posOfInt][i + 1] = interval[posOfInt][i] = ySet[i + 2];
					status[i + 1] = status[i] = posOfInt;
					//System.out.println("Extended Interval backwards to: " + (i + 1) + " " + (i));
				}
				else addInterval(i, i + 2, ySet[i]);
				
				addInterval(i + 1, i + 1, ySet[i + 1] - ySet[i + 2]);
			}
		}
//	*/
	
	/* Step 3: Identify 3-pattern (a,b,c) b = a + c */
//	/*
		for(i = 0; i < N-2; i++)
		{
			if((ySet[i] == 0)||(ySet[i + 1] == 0)||(ySet[i + 2] == 0)) continue;
			
			if(ySet[i + 1] == ySet[i + 2] + ySet[i])
			{
				//System.out.println("Found 3 pattern b = a + c: " + ySet[i] + ySet[i + 1] + ySet[i + 2]);
				posOfInt = status[i];
				if(posOfInt != -1)
				{
					interval[posOfInt][i + 1] = ySet[i];
					status[i + 1] = posOfInt;
				}
				else 
				addInterval(i, i + 1, ySet[i]);
				
				posOfInt = status[i + 2];
				if(posOfInt != -1)
				{
					interval[posOfInt][i + 1] = ySet[i + 2];
					status[i + 1] = posOfInt;
				}
				else 
				addInterval(i + 1, i + 2, ySet[i + 2]);
			}
		}
//	*/
		
	/* Step 4: Identify 4-pattern (a,b,c,d) 'b - a = c - d' */
	/*
		for(i = 0; i < N - 3; i++)
		{
			if((ySet[i] == 0)||(ySet[i + 1] == 0)||(ySet[i + 2] == 0)||(ySet[i + 3] == 0)) continue;
			
			if((ySet[i + 1] - ySet[i] == ySet[i + 2] - ySet[i + 3]) && 
				((ySet[i + 2] - ySet[i + 3]) > 0))
			{
				System.out.println("Found 4 pattern b - a = c - d: " + ySet[i] + ySet[i + 1] + ySet[i + 2] + ySet[i + 3]);
				posOfInt = status[i];
				if(posOfInt != -1)
				{
					interval[posOfInt][i + 1] = ySet[i];
					status[i + 1] = posOfInt;
				}
				else 
					addInterval(i, i + 1, ySet[i]);
				
				addInterval(i + 1, i + 2, ySet[i + 1] - ySet[i]);
				
				posOfInt = status[i + 3];
				if(posOfInt != -1)
				{
					interval[posOfInt][i + 2] = ySet[i + 3];
					status[i + 2] = posOfInt;
				}
				else 
					addInterval(i + 2, i + 3, ySet[i + 3]);
			}
		}
	*/	
		
		
	/* Step 5: Add intervals for remaining individual elements */		

		for(i = 0; i < N; i++)
		{
			if(status[i] == -1)
			{
				addInterval(i, i, ySet[i]);
			}
		}
		
	/* Step 6: Convert the interval array into WICOutput object */
		int start, end, index;
		boolean inMiddle = false;
		
		for(i = 0; i < numK; i++)
		{
			start = 0;
			end = 0;
			inMiddle = false;
			index = 0;
			for(j = 0; j < N; j++)
			{
				if((!inMiddle)&&(interval[i][j] > 0)) 
				{
					start = j + 1;
					inMiddle = true;
				}
				
				if((inMiddle)&&(interval[i][j] == 0))
				{
					end = j + 1;
					inMiddle = false;
					index = j - 1;
					break;
				}
				
				else if((inMiddle)&&(interval[i][j] != 0)&&(j == N - 1))
				{
					end = j + 2;
					inMiddle = false;
					index = N - 1; 
					break;
				}
			}
			solution.add(new int[]{start,end,interval[i][index]});
			//System.out.println(start + ", " + end + ", " + interval[i][index]);
		}

	/* Optimization of the Output */
		
		int[] list;
		int[] checklist;
		
		for(i = 0; i < numK; i++)
		{
			list = solution.get(i);
			for(j = 0; j < numK; j++)
			{
				checklist = solution.get(j);
				if((checklist[0] == list[1]) && (checklist[2] == list[2]))
				{
					//System.out.println("XXXXXXXXXX: " + " ");
				}
			}
		}
		
		//System.out.println("\nNumber of Intervals: " + numK);
		//printStatus();
		
		return new WICOutput(solution,solution.size());
	}

	private void addInterval(int start, int end, int c)
	{
		for(int i = start; i <= end; i++)
		{
			interval[numK][i] = c;
			status[i] = numK;
		}
		
		numK = numK + 1;
		
		//System.out.println("Added Interval Start:" + start + " End:" + end + " C:" + c + " ");
	}
	
	private void printStatus()
	{
		for(int i = 0; i < N; i++)
		{
			System.out.print(ySet[i] + " " );
		}
		
		for(int i = 0; i < numK; i++)
		{
			System.out.println();
			for(int j = 0; j < N; j++)
			{
				System.out.print(interval[i][j] + " ");
			}
		}
		System.out.println();
		for(int i = 0; i < N; i++)
		{
			System.out.print(status[i] + " " );
		}
	}
	
	private int findMin(int[] ySet)
	{
		int min = ySet[0];
		
		for (int i = 0; i < N; i++)
		{
			if(ySet[i] < min)
				min = ySet[i];
		}
		
		return min;
	}
	
}
